home *** CD-ROM | disk | FTP | other *** search
/ TeX 1995 July / TeX CD-ROM July 1995 (Disc 1)(Walnut Creek)(1995).ISO / graphics / pictex / tree.sty < prev   
Text File  |  1992-08-30  |  11KB  |  354 lines
  1. % Binary tree drawing in LaTeX using the PiCTeX macros.
  2. %
  3. % Edward M. Reingold (reingold@cs.uiuc.edu)
  4. % Nachum Dershowitz (nachum@cs.uiuc.edu)
  5. %
  6. \typeout{Binary Tree Macros.  Released 18 Jan 1991; modified 2 Apr 1992.}
  7. %
  8. % These macros are in the public domain.  You may use them and copy them at
  9. % will, provided you retain the authorship information.
  10. %
  11. %
  12. % USAGE: \tree[optional root symbol]{left subtree}{right subtree}
  13. %
  14. % For example,
  15. %
  16. %     \tree[X]
  17. %        {\setdots\tree[Z]
  18. %           {\setsolid\tree[Y]{a}{}}
  19. %           {\setsolid\tree{c}{d}}}
  20. %        {\tree
  21. %           {\tree{}{f}}
  22. %           {\tree{g}{h}}}
  23. %
  24. % The root symbol and leaves can be anything you can construct in LaTeX
  25. % or PiCTeX.  The trees constructed can be used in any context in LaTeX
  26. % or PiCTeX.  That is, you can have, say, tables of trees of equations.
  27. %
  28. %
  29. % WARNING: Do not use the tilde (~) as the first character in any subtree!
  30. %
  31. %
  32. % PARAMETERS: Feel free to change the following tree drawing parameters;
  33. %             these parameters can be reset even in the middle of a tree.
  34. %
  35. \newdimen\subtreesep \subtreesep=10pt   % Distance between nonempty subtrees
  36. \newdimen\levelsep   \levelsep=30pt     % Distance between successive levels
  37. \def\nodesymbol{$\bullet$}              % Default symbol for an internal node
  38. %                          Tree edges connecting to the default node symbol
  39. %                          will go to it's center.  Other tree edges will be
  40. %                          chopped off at a node's bounding box.
  41. %
  42. %
  43. % Here's an example that changes the parameters in the middle of the tree:
  44. %
  45. %     \subtreesep=15pt\levelsep=40pt
  46. %     \tree[\fbox{\subtreesep=5pt\levelsep=13pt\tree[o]{a}{a}}]
  47. %        {b}{b}
  48. %
  49. %
  50. % You can get triangular subtrees by using \triangle which has the format 
  51. %
  52. %      \triangle[optional apex label]{width}{height}
  53. %
  54. % For example,
  55. %
  56. %      \tree{\triangle[A]{2\subtreesep}{2\levelsep}}
  57. %           {\tree{\triangle{\subtreesep}{\levelsep}}
  58. %                 {\tree{\fbox{}}
  59. %                       {\fbox{}}}}
  60. %
  61. %
  62. % Don't fiddle with the stuff that follows; it's fairly delicate.
  63. %
  64. % Working variables
  65. %
  66. \catcode`@=11%
  67. \newdimen\halfsubtreesep % half the subtree separation
  68. %
  69. \newdimen\leftwd         % width of left subtree
  70. \newdimen\rightwd        % width of right subtree
  71. %
  72. \newcount\rootbullet     % flag indicating if root is the default bullet
  73. \newdimen\rootwd         % width of root
  74. \newdimen\rootht         % height of root
  75. \newdimen\rootdp         % depth of root
  76. %
  77. \newcount\leftrootbullet % flag indicating if left root is the default bullet
  78. \newdimen\leftrootht     % height of left subtree's root
  79. \newdimen\leftrootwd     % width of left subtree's root
  80. \newcount\rightrootbullet% flag indicating if right root is the default bullet
  81. \newdimen\rightrootht    % height of right subtree's root
  82. \newdimen\rightrootwd    % width of right subtree's root
  83. %
  84. \newdimen\@@root           % distance of root midpointfrom left edge of tree
  85. \newdimen\leftroot       % distance of root midpoint of left subtree
  86.                          % from left edge of tree
  87. \newdimen\rightroot      % distance of root midpoint of right subtree
  88.                          % from left edge of tree
  89. %
  90. \newcount\leafnode       % flag indicating if subtree just placed is a leaf
  91. %
  92. \newdimen\rootxpos       % x-cooordinate of the root midpoint
  93. \newdimen\leftrootpos    % position of the root of the left subtree
  94. \newdimen\rightrootpos   % position of the root of the right subtree
  95. \newdimen\leftpos        % position of the NE corner of the left subtree
  96. \newdimen\rightpos       % position of the NW corner of the right subtree
  97. %
  98. \newbox\rootnode         % the root node, as placed
  99. \newbox\leftsubtree      % the left subtree, as placed
  100. \newbox\rightsubtree     % the right subtree, as placed
  101. %
  102. \newdimen\xa             % (\xa,\ya) = coordinates of the point on the root
  103. \newdimen\ya             % node at which to connect the line to a child
  104. \newdimen\xb             % (\xb,\yb) = coordinates of the point on the child
  105. \newdimen\yb             % at which to connect the line to the parent
  106. %
  107. \let\ifnextchar=\@ifnextchar%
  108. \def\tree{\ignorespaces%
  109. \def\tree{\ifnextchar[{\treey}{\treex}}%
  110. %
  111. \setdimensionmode%
  112. \setlinear%
  113. %
  114. \@ifnextchar[{\treey}{\treex}%
  115. }%
  116. %
  117. \long\def\treex#1#2{\itree{#1}{#2}{\nodesymbol}}  % use default node symbol
  118. \long\def\treey[#1]#2#3{\itree{#2}{#3}{#1}}       % use specified node symbol
  119. %
  120. \long\def\itree#1#2#3{\ignorespaces  % #1=left, #2=right, #3=root
  121. %
  122. \halfsubtreesep=\subtreesep     % Do this calculation for each node so its...
  123. \divide\halfsubtreesep by 2     % ...value can vary throughout the tree
  124. %
  125. \ignorespaces%
  126. %
  127. % Recursively draw nonempty left subtree
  128. %
  129. \ifx ~#1~\ignorespaces%
  130.  \else%
  131.    \leafnode=1  % Assume left subtree is a leaf
  132.    \setbox\leftsubtree=\hbox{#1}\ignorespaces
  133.    \leftwd=\wd\leftsubtree%
  134.    \leftroot=\@@root%
  135.    \leftrootbullet=\rootbullet%
  136.    \leftrootht=\rootht%
  137.    \leftrootwd=\rootwd%
  138.    \ifnum \leafnode=1%
  139.       \leftroot=\leftwd%
  140.       \divide\leftroot by 2%
  141.       \leftrootbullet=0%
  142.       \leftrootht=\ht\leftsubtree%
  143.       \advance\leftrootht by \dp\leftsubtree%
  144.       \leftrootwd=\leftwd%
  145.    \fi%
  146. \fi%
  147. %
  148. % Recursively draw nonempty right subtree
  149. %
  150. \ifx ~#2~\ignorespaces%
  151.  \else%
  152.    \leafnode=1  % Assume right subtree is a leaf
  153.    \setbox\rightsubtree=\hbox{#2}\ignorespaces%
  154.    \rightwd=\wd\rightsubtree%
  155.    \rightroot=\@@root%
  156.    \rightrootbullet=\rootbullet%
  157.    \rightrootht=\rootht%
  158.    \rightrootwd=\rootwd%
  159.    \ifnum \leafnode=1%
  160.       \rightroot=\rightwd%
  161.       \divide\rightroot by 2%
  162.       \rightrootbullet=0%
  163.       \rightrootht=\ht\rightsubtree%
  164.       \advance\rightrootht by \dp\rightsubtree%
  165.       \rightrootwd=\rightwd%
  166.    \fi%
  167. \fi%
  168. %
  169. % In the case of empty subtrees, give artificial values for those empty
  170. % trees so that the later calculations are done properly.
  171. %
  172. \ifx ~#1#2~\ignorespaces        %  Both subtrees empty
  173.    \rightroot=0pt%
  174.    \leftroot=-\halfsubtreesep%
  175.    \leftwd=-\halfsubtreesep%
  176. \else\ifx ~#1~\ignorespaces     %  Left subtree empty, right subtree not empty
  177.    \leftroot=\rightroot%
  178.    \advance\leftroot by -\subtreesep%
  179.    \leftwd=-\subtreesep%
  180. \else\ifx ~#2~\ignorespaces     %  Right subtree empty, left subtree not empty
  181.    \rightroot=\leftroot%
  182.    \advance\rightroot by -\leftwd%
  183. \fi\fi\fi%
  184. %
  185. % With the subtrees done, now do the root node
  186. %
  187. \setbox\rootnode=\hbox{\setcoordinatemode #3}\ignorespaces%
  188. \global\rootwd=\wd\rootnode%
  189. \global\rootht=\ht\rootnode%
  190. \global\advance\rootht by \dp\rootnode%
  191. \ifx \nodesymbol#3\ignorespaces%
  192.     \global\rootbullet=1%
  193.   \else\ignorespaces%
  194.     \global\rootbullet=0%
  195. \fi%
  196. %
  197. % Find distance of the root midpoint from left edge of the tree
  198. %
  199. \global\@@root=\leftroot%
  200. \global\advance\@@root by \rightroot%
  201. \global\advance\@@root by \leftwd%
  202. \global\advance\@@root by \subtreesep%
  203. \ifdim \@@root<\rootwd \global\@@root=\rootwd \fi%
  204. \global\divide\@@root by 2%
  205. %
  206. % Indicate this root and all its ancestors are not a leaves
  207. %
  208. \global\leafnode=0%
  209. %
  210. % Find positions of the root and those of the roots of the subtrees
  211. %
  212. \leftrootpos=\leftroot%
  213. \advance\leftrootpos by -\leftwd%
  214. \advance\leftrootpos by -\halfsubtreesep%
  215. %
  216. \rightrootpos=\rightroot%
  217. \advance\rightrootpos by \halfsubtreesep%
  218. %
  219. \rootxpos=\leftrootpos%
  220. \advance\rootxpos by \rightrootpos%
  221. \divide\rootxpos by 2%
  222. %
  223. \leftpos=0pt%
  224. \advance\leftpos by \leftrootht%
  225. \divide\leftpos by 2%
  226. %
  227. \rightpos=0pt%
  228. \advance\rightpos by \rightrootht%
  229. \divide\rightpos by 2%
  230. %
  231. % Now the root is a box of width \rootwd and total height \rootht, centered
  232. % at (\rootxpos,\levelsep); the root of the left subtree is a box of
  233. % width \leftrootwd and total height \leftrootht, centered at
  234. % (\leftrootpos,0); the root of the right subtree is a box of width
  235. % \rightrootwd and total height \rightrootht, centered at (\rightrootpos,0).
  236. %
  237. %
  238. \beginpicture
  239. %
  240. \put {\box\rootnode} at {\rootxpos} {\levelsep}     % Draw the root
  241. %
  242. \ifx ~#1~\else                                      % Draw the left subtree
  243.    \put {\box\leftsubtree} [rt] at {-\halfsubtreesep} {\leftpos}
  244.    \xa=\rootxpos%
  245.    \ya=\levelsep%
  246.    \ifnum\rootbullet=0%
  247.       \chop{\rootxpos}{\levelsep}{-\rootwd}{\rootht}{\leftrootpos}{0}%
  248.            {\xa}{\ya}%
  249.    \fi%
  250.    \xb=\leftrootpos%
  251.    \yb=0pt%
  252.    \ifnum\leftrootbullet=0%
  253.       \chop{\leftrootpos}{0}{\leftrootwd}{-\leftrootht}{\rootxpos}{\levelsep}%
  254.            {\xb}{\yb}%
  255.    \fi%
  256.    \plot {\xa} {\ya}  {\xb} {\yb} /%
  257. \fi%
  258. %
  259. \ifx ~#2~\else                                      % Draw the right subtree
  260.    \put {\box\rightsubtree} [lt] at {\halfsubtreesep} {\rightpos}
  261.    \xa=\rootxpos%
  262.    \ya=\levelsep%
  263.    \ifnum\rootbullet=0%
  264.       \chop{\rootxpos}{\levelsep}{\rootwd}{\rootht}{\rightrootpos}{0}%
  265.            {\xa}{\ya}%
  266.    \fi%
  267.    \xb=\rightrootpos%
  268.    \yb=0pt%
  269.    \ifnum\rightrootbullet=0%
  270.       \chop{\rightrootpos}{0}{-\rightrootwd}{-\rightrootht}{\rootxpos}%
  271.            {\levelsep}{\xb}{\yb}%
  272.    \fi
  273.    \plot {\xa} {\ya}  {\xb} {\yb} /%
  274. \fi%
  275. %
  276. % Draw the bottom of the triangle, when appropriate.
  277. %
  278. \ifx#1. \ifx#2. \plot {\leftrootpos} {0pt} {\rightrootpos} {0pt} / \fi\fi%
  279. %
  280. \endpicture%
  281. }%
  282. %
  283. \long\def\triangle{\ifnextchar[{\triangley}{\trianglex}}%
  284. \long\def\trianglex#1#2{\itriangle{#1}{#2}{}}       % use empty apex symbol
  285. \long\def\triangley[#1]#2#3{\itriangle{#2}{#3}{#1}} % use specified apex symbol
  286. \long\def\itriangle#1#2#3{%  A triangle #1 wide and #2 high, #3 at apex
  287.    \subtreesep=#1%
  288.    \levelsep=#2%
  289.    \tree[#3]{.}{.}%
  290. }%
  291. %
  292. \newcount\@@x%  Scratch counters used in the computations of \chop
  293. \newcount\@@y%  to find the location on the border of a node's bounding
  294. \newcount\@@a%  box at which to attach a line aimed at a target point
  295. \newcount\@@b%  from the center of the box.
  296. \newcount\@@c%
  297. \newcount\@@d%  It would be better to do all these calculation in dimen's
  298. \newcount\@@e%  instead of counters, but so many dimen's are used above
  299. \newcount\@@f%  that to do so would make running out of dimen's very probable.
  300. \newcount\@@g%  
  301. \newcount\@@h%  Forgive us for not explaining the following computations;
  302. \newcount\@@l%  they're based on elementary analytical geometry.
  303. %
  304. \def\chop#1#2#3#4#5#6#7#8{\ignorespaces%
  305.                           % (#1,#2) = coordinates of center of bounding box
  306.                           % #3 x #4 = width x height of bounding box
  307.                           % (#5,#6) = coordinates of target point
  308.                           % (#7,#8) = coordinates of computed intersection
  309.                           %           point
  310. %
  311. \@@a=#1\divide \@@a by 10000%  Scale down to prevent arithmetic overflow.
  312. \@@b=#2\divide \@@b by 10000%
  313. \@@c=#3\divide \@@c by 10000%
  314. \@@d=#4\divide \@@d by 10000%
  315. \@@e=#5\divide \@@e by 10000%
  316. \@@f=#6\divide \@@f by 10000%
  317. %
  318. \@@l=-\@@f\advance\@@l by \@@b%
  319. %%
  320. \@@y=-\@@d%
  321. \divide \@@y by 2%
  322. \advance\@@y by \@@b%
  323. %%
  324. \@@g=\@@c%
  325. \divide \@@g by 2%
  326. \advance\@@g by \@@a%
  327. %%
  328. \@@x=-\@@a%
  329. \advance\@@x by \@@e%
  330. \multiply\@@x by \@@d%
  331. \divide\@@x by \@@l%
  332. \divide\@@x by 2%
  333. \advance \@@x by \@@a%
  334. %%
  335. \count255=-\@@a%
  336. \advance\count255 by \@@e%
  337. \multiply\count255 by 2%
  338. \@@h=-\@@c%
  339. \multiply \@@h by \@@l%
  340. \divide \@@h by \count255%
  341. \advance \@@h by \@@b%
  342. %
  343. \ifnum #5>#1%
  344.    \ifnum\@@x>\@@g\else\@@g=\@@x\@@h=\@@y\fi%
  345. \else%
  346.    \ifnum\@@x<\@@g\else\@@g=\@@x\@@h=\@@y\fi%
  347. \fi%
  348. \multiply\@@g by 10000%  Scale back up
  349. \multiply\@@h by 10000%
  350. \global#7=\@@g sp%
  351. \global#8=\@@h sp%
  352. }%
  353. \catcode`@=12%
  354.